package labuladong.chapter0;

public class ChapterOne {

    /**
     * 单链表的基本技巧
     * https://labuladong.online/algo/essential-technique/linked-list-skills-summary/#%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%9C%89%E5%BA%8F%E9%93%BE%E8%A1%A8
     */

    public static void main(String[] args) {
        //xxx
    }

    //1、合并两个有序链表(都是小到大的顺序)：
    ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //虚拟头节点可以降低复杂度，否则需要处理指针p为空的边界情况
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        ListNode p1 = list1;
        ListNode p2 = list2;
        //依次比较p1或者p2，小的放前面
        while (p1 != null && p2 != null) {
            if (p1.val > p2.val) {
                p.next = p2;
                p2 = p2.next;
            } else {
                p.next = p1;
                p1 = p1.next;
            }
            p = p.next;
        }
        //还存在p1或者p2单独留下的场景需要考虑
        if (p1 != null) {
            p.next = p1;
        }
        if (p2 != null) {
            p.next = p2;
        }
        return dummy.next;
    }

    //2、单链表的分解
    ListNode partition(ListNode head, int x) {
        ListNode dummyL = new ListNode(-1);
        ListNode dummyR = new ListNode(-1);
        ListNode p1 = dummyL;
        ListNode p2 = dummyR;
        ListNode curNode = head;
        while (curNode != null) {
            if (curNode.val < x) {
                p1.next = curNode;
                p1 = p1.next;
            } else {
                p2.next = curNode;
                p2 = p2.next;
            }
            //不能直接让curNode指针前进，会影响已经处理的链表的结点指向（因为是引用关系）
            //curNode = curNode.next;
            //需要断开原链表每个节点的next指针
            ListNode temp = curNode.next;
            curNode.next = null;
            curNode = temp;
        }
        p1.next = dummyR.next;
        return dummyL.next;
    }

    // 单链表倒数第k个结点：双指针法
    ListNode findFromEnd(ListNode head, int k) {
        //先让p1结点走k个位置
        ListNode p1 = head;
        for (int i = 0; i < k ; i++) {
            p1 = p1.next;
        }
        //p1走完，让p2指向头节点，p2跟着p1走到末尾，此时p2位于n-k+1位置，即倒数第k个结点
        ListNode p2 = head;
        while (p1.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }
}
